#pragma once
#include <unordered_map>
#include <vector>
#include <iostream>
using namespace std;

class UnionFindSet
{
public:
	// size：元素总个数
	// 将ufs初始化为-1，更新时累加，容易统计人数
	UnionFindSet(int size)
		: _ufs(size, -1)
	{
	}
	// 找到 x 元素的根节点
	size_t findRoot(int x)
	{
		// 获取x下标对应的元素，如果该元素为非负数，则x不是根
		// 继续向上找
		int root = x;
		while (_ufs[root] >= 0)
			root = _ufs[root];

		// 这里可以进行路径压缩：
		// 什么是路径压缩？在合并集合的过程中，树的高度会越来越高，此时可以进行压缩路径
		// 压缩路径是指将下层的集合元素的双亲直接更改为根节点
		// 路径压缩思路：找到根节点后，再次从x遍历，更改双亲

		// 路径压缩
		while (x != root)
		{
			int parent = _ufs[x];
			_ufs[x] = root;
			x = parent;
		}

		return x;
	}

	// 将两个元素合并到一个集合
	bool Union(int x, int y)
	{
		// 1.判定两个元素是否是同一个集合
		int root1 = findRoot(x);
		int root2 = findRoot(y);
		if (root1 == root2)
			return true;

		// 两个集合合并优化：让小的集合合并到大的集合
		// 为什么？ 都是两层的集合，小的合并过去，第三层数量少，如果大的合并过去第三层数量多
		if (abs(_ufs[root1]) < abs(_ufs[root2]))
			swap(root1, root2);

		// roo1人数进行累加，更新root2指向元素的值
		// root2 表示小的，roo1表示大的
		_ufs[root1] += _ufs[root2];
		_ufs[root2] = root1;
	}

	// 判定两个元素是否为同一个集合
	bool IsSameSet(int x, int y)
	{
		int root1 = findRoot(x);
		int root2 = findRoot(y);
		return root1 == root2 ? true : false;
	}

	// 集合个数
	size_t Size()
	{
		int cnt = 0;
		for (int i = 0; i < _ufs.size(); i++)
		{
			if (_ufs[i] < 0)
				cnt++;
		}
		return cnt;
	}

private:
	vector<int> _ufs;

	// 如果题目没有直接给定编号，而是给定字符串表示一个元素
	// 则需要使用哈希建立 字符串-下标 的映射关系
	// 让下标作为编号

	// unordered_map<string,int> _index;
	// unordered_map<int,string> _name;
};

void test_union()
{
	UnionFindSet ufs(10);
	ufs.Union(0, 1);
	ufs.Union(1, 2);
	ufs.Union(2, 3);

	ufs.Union(5, 6);
	ufs.Union(6, 7);


	ufs.Union(2, 6);
	int a;
}
void test_compass()
{
	UnionFindSet ufs(10);
	ufs.Union(0, 1);
	ufs.Union(1, 2);

	ufs.Union(3, 4);
	ufs.Union(4, 5);

	ufs.Union(6, 7);
	ufs.Union(7, 8);


	ufs.Union(3, 6);
	ufs.Union(1, 3);
	ufs.findRoot(8);
	int a;
}